package cn.algorithm;

/**
 * @author: lizemin
 * @version: 1.0
 */
public class Test04 {
    //通过二分查找法

    /**
     *
     * @param x
     * @return
     */
    public static int mySqrt(int x) {//总而言之, 具体思路是调整上下限的值,来缩小查找范围.
        int min = 0, max = x, result = -1;//将r设置上限值, 初始最大为x, l为最小值.
        while (min <= max) {
            int mid = 1 + (max - 1) / 2;//将不断变化的中间值设为上限值.
            if ((long) mid * mid <= x) {//如果中间值小了, 那就将这个中间值设置成下限值.
                result = mid;
                min = mid + 1;//同时上限值
            } else {
                max = mid - 1;
            }
        }
        return result;

    }

    //这是一个main方法,是程序的入口
    public static void main(String[] args) {
        int sqrt = mySqrt(100);
        System.out.println(sqrt);

    }
    class Solution {
        public int mySqrt(int x) {
            int l = 0, r = x, ans = -1;
            while (l <= r) {
                int mid = l + (r - l) / 2;
                if ((long) mid * mid <= x) {
                    ans = mid;
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
            return ans;
        }
    }

}
